package application.sudoku;

public class SudokuSolver {
    private char[][] board;
    public SudokuSolver() {  }
    public SudokuSolver(Sudoku sudoku) {
        this.setSudoku(sudoku);
    }
    public void setSudoku(Sudoku sudoku) {
        this.board = new char[9][9];
        for (int i = 0; i < 9; ++i) {
            for (int j = 0; j < 9; ++j) {
                this.board[i][j] = sudoku.board[i][j];
            }
        }
    }
    public Sudoku solve() {
        if (!backtrace(0, 0)) {
            return null;
        }
        return new Sudoku(this.board);
    }
    private boolean backtrace(int row, int col) {
        if (col == 9) {
            return this.backtrace(row+1, 0);
        }
        if (row == 9) {
            return true;
        }
        if (this.board[row][col] != '.') {
            return this.backtrace(row, col+1);
        }
        for (char c = '1'; c <= '9'; ++c) {
            if ( !this.isValid(row, col, c) ) {
                continue;
            }
            this.board[row][col] = c;
            if (this.backtrace(row, col+1)) {
                return true;
            }
            this.board[row][col] = '.';
        }
        return false;
    }
    private boolean isValid(int row, int col, char n) {
        for (int i = 0; i < 9; ++i) {
            // 检查行是否存在重复
            if (this.board[row][i] == n) {
                return false;
            }
            // 检查列是否存在重复
            if (this.board[i][col] == n) {
                return false;
            }
            // 检查 3*3 方框内是否存在重复
            if (this.board[(row/3)*3+i/3][(col/3)*3+i%3] == n) {
                return false;
            }
        }
        return true;
    }
}
